package algorithm7.leetcode.每日一题.YEAR2023.month6;

import lombok.ToString;
import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @Author: permission
 * @Date: 2023/6/11 11:11
 * @Version: 1.0
 * @ClassName: DAY20230611_LC1171
 * @Description:
 */
public class DAY20230611_LC1171 {

    public ListNode removeZeroSumSublists(ListNode head) {
        return handle1(head);
    }

    private ListNode handle1(ListNode head) {
        ListNode prefix = new ListNode(0, head);
        // <和， 节点>
        HashMap<Integer, ListNode> map = new HashMap<>();
        int sum = 0;
        for (ListNode node = prefix; node != null; node = node.next) {
            sum += node.val;
            map.put(sum, node);
        }
        sum = 0;
        for (ListNode node = prefix; node != null; node = node.next) {
            sum += node.val;
            node.next = map.get(sum).next;
        }
        return prefix.next;
    }

/*
1171. 从链表中删去总和值为零的连续节点
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
 */

    @Test
    void t() {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(-3);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(1);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        ListNode res = removeZeroSumSublists(head);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {

        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
